Cuts3vm: a fast semi-supervised svm algorithm
Bin Zhao
Fei Wang
Changshui Zhang
<i>Semi-supervised support vector machine (S3VM)</i> attempts to learn a decision boundary that traverses through low data density regions by maximizing the margin over labeled and unlabeled examples. Traditionally, <i>S3VM</i> is formulated as a non-convex integer programming problem and is thus difficult to solve. In this paper, we propose the <i>cutting plane semi-supervised support vector machine (CutS3VM)</i> algorithm, to solve the <i>S3VM</i> problem. Specifically, we construct a nested sequence of successively tighter relaxations of the original S3VM problem, and each optimization problem in this sequence could be efficiently solved using the <i>constrained concave-convex procedure (CCCP)</i>. Moreover, we prove theoretically that the <i>CutS3VM</i> algorithm takes time O(sn) to converge with guaranteed accuracy, where n is the total number of samples in the dataset and s is the average number of non-zero features, i.e. the sparsity. Experimental evaluations on several real world datasets show that <i>CutS3VM</i> performs better than existing <i>S3VM</i> methods, both in efficiency and accuracy.
